213. House Robber II
Medium

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

 

Example 1:

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Example 2:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 3:

Input: nums = [0]
Output: 0

 

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000
Accepted
250,324
Submissions
660,085
Seen this question in a real interview before?
Companies
Related Topics
Show Hint 1
Since House[1] and House[n] are adjacent, they cannot be robbed together. Therefore, the problem becomes to rob either House[1]-House[n-1] or House[2]-House[n], depending on which choice offers more money. Now the problem has degenerated to the House Robber, which is already been solved.

Average Rating: 4.17 (36 votes)

Premium

Solution

This problem is a minor extension to the original House Robber Problem. The only difference is that the first and the last houses are adjacent to each other and therefore, if the thief has robbed the first house, they cannot steal the last house and vice versa. As Hint 1 in the question suggests, "the problem becomes to rob either House[1]-House[n-1] or House[2]-House[n], depending on which choice offers more money. Now the problem has degenerated to the House Robber".


Approach 1: Dynamic Programming

Intuition

Assume we have nums of [7,4,1,9,3,8,6,5] as shown in the figure. Since the start house and last house are adjacent to each other, if the thief decides to rob the start house 7, they cannot rob the last house 5. Similarly, if they select last house 5, they have to start from a house with value 4. Therefore, the final solution that we are looking for is to take the maximum value the thief can rob between houses of list [7,4,1,9,3,8,6] and [4,1,9,3,8,6,5]. For each of the lists, all we need to do is to figure the maximum value the thief can get using the approach in the original House Robber Problem.

alt text

Solving Original House Robber Problem with Dynamic Programming

Trivial cases:

  • If there is one house, the answer is the value of that house.
  • If there are two houses, the answer is max(house1, house2).
  • If there are three houses, you can either pick the middle house or the sum of the first and the last house. Therefore, it boils down to max(house3 + house1, house2).

To make the example more illustrative, imagine two thieves (t1 and t2) coordinating a grand robbery. They are equipped with walkie-talkies to communicate the values of houses to each other.

  • Before entering any of the houses, both t1 and t2 have values of zero.

  • t1, enters the first house and record the value of the house. If that is the only house to rob, they can rob this house and be done with it.

  • If there is more than one house, t1 will leave a note of maximum value reaped until this point (which is just the value of the first house) and move to the next house while t2 moves into the house t1 was in. Now, t1 and t2 are going to communicate over the walkie-talkie to ask who has the most value. At this point, t2 will read the note left by t1 when the values are compared. If they have only two houses to rob, they would rob the house with the most value and be done with it.

  • If there are three houses, t1 will leave a note of the maximum value reaped until this point and move to the next house. Then t1 will compare the value of the sum of the current house and the house which t2 is in with the value of the house t1 was in. The maximum value between those two will be chosen and t2 will move into the house next to it.

  • If there are four houses, t1 will leave a note of the maximum value reaped until this point and move to the next house. Then t1 will compare the value of the sum of the current house and the house which t2 is in with the value of the house t1 was in. The maximum value between those two will be chosen and t2 will move into the house next to it.

  • This procedure is done over and over again as long as there are houses in nums. If t1 has reached to the end of nums, t1 should have reaped the maximum amount obtainable from houses in nums.

Current
1 / 22

Implementation

Complexity Analysis

  • Time complexity : O(N)O(N) where NN is the size of nums. We are accumulating results as we are scanning nums.

  • Space complexity : O(1)O(1) since we are not consuming additional space other than variables for two previous results and a temporary variable to hold one of the previous results.

Report Article Issue

Comments: 13
acbthisisit's avatar
Read More

The hint on the problem says it all

13
Reply
Share
Report
SrihariShastry's avatar
Read More

If there are three houses, you can either pick the middle house or the sum of the first and the last house. Therefore, it boils down to max(house3 + house1, house2).

isn't house 3 and house 1 adjacent to each other? in case of three houses, shouldn't we pick the highest of the three houses?

34
Show 3 replies
Reply
Share
Report
Veluga's avatar
Read More

Space complexity for the Python solution should be O(N) since list slicing creates a new list, in both cases of length N-1.

1
Show 2 replies
Reply
Share
Report
evgeni-nabokov's avatar
Read More

It could be done in one loop, not in two.

1
Show 1 reply
Reply
Share
Report
weidingh's avatar
Read More

If there are only two houses, shouldn't we get 0 since we cannot rob adjacent houses?

0
Show 1 reply
Reply
Share
Report
sjkoo's avatar
Read More

Slicing is still a shallow copy. Therefore, space is O(1)

0
Show 1 reply
Reply
Share
Report
lugax16's avatar
Read More

Can anyone please help to understand this question? if i have a linear list [1, 3, 4].My understanding you can only rob( house1 + house4) and not house3 +( house1 + house4).Since house is at the middle of both 1 and 4

0
Reply
Share
Report
kapilsh's avatar
Read More

The variable names are so bad in most leetcode solutions..

0
Reply
Share
Report
cepie's avatar
Read More

Space complexity is incorrect as of 23-Apr-21. It should be O(N) because slicing the list creates a copy. It is possible to achieve O(1) by rewriting rob_simple to accept start and end indexes.

0
Reply
Share
Report
rajatIIT's avatar
Read More

Dynamic or Greedy?

0
Show 1 reply
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
05/31/2021 08:44Accepted0 ms7.7 MBcpp
06/08/2020 13:36Accepted8 ms7.8 MBcpp
06/08/2020 13:35Runtime ErrorN/AN/Acpp
06/08/2020 13:34Runtime ErrorN/AN/Acpp
06/08/2020 13:33Wrong AnswerN/AN/Acpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
This list is empty.